package primaryAlgorithm.shuffleArray;

import java.util.ArrayList;
import java.util.Random;

/**
 * @Date 2020/03/24
 * @author 王光浩
 * @Thinking 使用暴力法（这是一个全排列问题）
 * @Analysis 时间复杂度O（n^2)，空间复杂度O（n）
 */
public class MyMethodTwo {
	private int[] original;
	private ArrayList<Integer> shu;
	private Random random=new Random(); //获取随机数
	 public MyMethodTwo(int[] nums) {
		 original=nums;
		 shu=new ArrayList<Integer>(nums.length);
	 }
	    
	  /** Resets the array to its original configuration and return it. */
	  public int[] reset() {
		  return original;
	  }
	    
	  /** Returns a random shuffling of the array. */
	  public int[] shuffle() {
		  for(int tem:original)
			  shu.add(tem);
		  int[] ret=new int[original.length];
		  for(int i=0;i<original.length;i++) {
			  int tem=random.nextInt(shu.size());
			  ret[i]=shu.get(tem);
			  shu.remove(tem);  //时间复杂度O（n）
		  }
		  return ret;
	  }
}
